package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         17,
		Discription: "电话号码的组合",
		Level:       2,
		Labels: map[string]int{
			"递归":  1,
			"哈希表": 1,
			"字符串": 1,
		},
	})
}

func LetterCombinations(digits string) []string {
	if digits == "" {
		return []string{}
	}
	res := make([]string, 0)
	length := len(digits)

	var travel func(int, string)
	travel = func(start int, str string) {
		if start >= length {
			res = append(res, str)
			return
		}

		//初始化回溯值
		if start == 0 {
			str = ""
		}
		characters := match(digits[start])
		for _, ch := range characters {
			travel(start+1, str+ch)
		}
	}

	travel(0, digits)
	return res
}

func match(num byte) []string {
	switch num {
	case '2':
		return []string{"a", "b", "c"}
	case '3':
		return []string{"d", "e", "f"}
	case '4':
		return []string{"g", "h", "i"}
	case '5':
		return []string{"j", "k", "l"}
	case '6':
		return []string{"m", "n", "o"}
	case '7':
		return []string{"p", "q", "r", "s"}
	case '8':
		return []string{"t", "u", "v"}
	case '9':
		return []string{"w", "x", "y", "z"}
	default:
		return []string{}
	}
}
